Various methods of image compression are known in the art. These methods can be categorized generally as lossy and lossless. When lossless compression is used, the original image can be reproduced exactly upon decompression. In general, however, lossy methods achieve higher compression ratios, i.e., smaller compressed image files for a given original image.
One of the most popular methods for lossless compression of gray-scale and color images is the Lempel-Ziv-Welch (LZW) algorithm. This algorithm is described in U.S. Pat. Nos. 4,558,302 and 5,642,112, whose disclosures are incorporated herein by reference. LZW compression uses a dictionary for storing strings of data characters encountered in the input to the algorithm. The input stream, typically a sequence of pixel values in an image, is searched by comparing segments of the input stream to the strings stored in the dictionary in order to find the longest matching string. The dictionary is then augmented by storing an extended string, comprising the longest matching string with the addition of the next input data character following the longest matching segment in the input stream. This procedure continues until the entire image has been compressed.